package BinarySearchTree;

public class BinarySearchTree {
	private Node root = null;
	//constructor
	public BinarySearchTree(){
	
	}
	/** 
	   Returns true if the given target is in the binary tree. 
	   Uses a recursive helper. 
	  */ 		
	public boolean lookup(int data){
		return (lookup(root,data));
	}
		
	public boolean lookup (Node node,int data){
		if(node == null){
			return false;
		}
		if(data == node.data){
			return true;
			
		} else if(data < node.data){
			
			return(lookup(node.left,data));
		
		}else {
			return(lookup(node.right,data));
		}
	}
	/** 
	   Inserts the given data into the binary tree. 
	   Uses a recursive helper. 
	  */
	public void insert(int data){
		root = insert(root,data);
	}
	
	/** 
	   Recursive insert -- given a node pointer, recur down and 
	   insert the given data into the tree. Returns the new 
	   node pointer (the standard way to communicate 
	   a changed pointer back to the caller). 
	  */ 
	public Node insert(Node node,int data){
		if(node==null){
			node = new Node(data);
			
		}else {
			if(data<node.data){
				node.left = insert(node.left,data);
		
			}else{
				node.right = insert(node.right,data);
			}
		}
		return(node);
	}
	

	/**
	 * Binary Tree problems Practice:
	 * 1)Build 123 using three pointer variables. 
	 *  
	 *  2 
	   / \ 
	  1   3
	 * 
	 * 
	 */
	 
	public void build123a(){
		root = new Node(2);
		Node lChild = new Node(1);
		Node rChild = new Node(2);
		root.left = lChild;
		root.right = rChild;
	}
	
	/** 
	 Build 123 using only one pointer variable. 
	*/ 
	public void build123b(){
		root = new Node(2);
		root.left = new Node(1);
		root.right = new Node(3);
	}
	
	/** 
	 Build 123 by calling insert() three times. 
	 Note that the '2' must be inserted first. 
	*/
	public void build123c(){
		root = null;
		root= insert(root,2);
		root = insert(root,1);
		root = insert(root,3);
	}
	
	/** 
	 Returns the number of nodes in the tree. 
	 Uses a recursive helper that recurs 
	 down the tree and counts the nodes. 
	*/
	public int size(){
		return(size(root));
	}
	
	public int size(Node node){
		if(node == null){
			return(0);
		}else{
			return(size(node.left)+1+size(node.right));
		}
	}
	
	/** 
	 * Given a binary tree, compute its "maxDepth" -- the number of nodes along 
	 the longest path from
	  the root node down to the farthest leaf node.
	  Returns the max root-to-leaf depth of the tree. 
	 Uses a recursive helper that recurs down to find 
	 the max depth. 
	*/ 
	public int maxDepth(){
		return maxDepth(root);
	}
	
	public int maxDepth(Node node){
		if(node ==null){
			return(0);
			
		}else{
			int lDepth = maxDepth(node.left);
			int rDepth = maxDepth(node.right);
			//use the larger+ 1
			return(Math.max(lDepth,rDepth)+1);
		}
	}
	
	/** 
	 * Given a non-empty binary search tree (an ordered binary tree), return the minimum data
	 *  value found in that tree. Note that it is not necessary to search the entire tree. 
	 *  
	 Returns the min value in a non-empty binary search tree. 
	 Uses a helper method that iterates to the left to find 
	 the min value. 
	 
	 A maxValue() function is structurally very similar to this function
	*/ 
	public int minValue(){
		return (minValue(root));
	}
	
	public int minValue(Node node){
		Node current = node;
		while (current.left!= null){
			current = current.left;
		}
		return(current.data);
	}
	/** 
	 * 	 
	 A maxValue() function is structurally very similar to this function
	*/ 
	public int maxValue(){
		return(maxValue(root));
	}
	
	public int maxValue(Node node){
		Node current = node;
		while(current.right != null){
			current = current.right;
		}
		return(current.data);
	}
	
	/** 
	 * 4 
      / \ 
     2   5 
    / \ 
   1   3
	output "1 2 3 4 5".
	 Uses a recursive helper to do the traversal. 
	*/ 
	public void printTree(){
		printTree(root);
		System.out.println();
	}
	
    public void printTree(Node node){
    	if(node == null) {
    		return;
    	}
    	//left,node itself,right
    	printTree(node.left);
    	System.out.print(node.data+" ");
    	printTree(node.right);
    }
	
    /** 
     * 4 
      / \ 
     2   5 
    / \ 
   1   3
    output "1 3 2 5 4"
    Prints the node values in the "postorder" order. 
    Uses a recursive helper to do the traversal. 
   */ 
	public void printPostorder(){
		printPostorder(root);
		System.out.println();
		
	}
	public void printPostorder(Node node){
		if(node == null){
			return;
		}
		//first recur on both subtrees
		printPostorder(node.left);
		printPostorder(node.right);
		//then deal with the node
		System.out.print(node.data+" ");
	}
	
	
	/** 
	 *  Given a tree and a sum, returns true if there is a path from the root 
	 down to a leaf, such that adding up all the values along the path 
	 equals the given sum.
	 Strategy: subtract the node value from the sum when recurring down, 
	 and check to see if the sum is 0 when you run out of tree. 
	 
	 		  5 
             / \ 
            4   8 
           /   / \ 
          11  13  4 
         /  \      \ 
        7    2      1
        
	 * "root-to-leaf path" 
	 * ---	 path 1: 5 4 11 7 
   			path 2: 5 4 11 2 
   			path 3: 5 8 13 
   			path 4: 5 8 4 1
   	the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27.	
	
	*/ 
	public boolean hasPathSum(int sum){
		return(hasPathSum(root,sum));
	}
	
	public boolean hasPathSum(Node node,int sum){
		//return true if we run out of tree and sum==0
		if(node==null){
			return(sum ==0);
		
		}else{
			// otherwise check both subtrees 
			int subSum = sum -node.data;
			return(hasPathSum(node.left,subSum))||hasPathSum(node.right,subSum);
			
		}
		
	}
	/** 
	 * 
	 Given a binary tree, prints out all of its root-to-leaf 
	 paths, one per line. Uses a recursive helper to do the work. 
	 
	  probably the best solution is to create a recursive helper function 
	  printPathsRecur(node, int path[], int pathLen), where the path array 
	  communicates the sequence of nodes that led up to the current call. 
	  Alternately, the problem may be solved bottom-up, with each node returning 
	  its list of paths.
	*/ 
	public void printPaths(){
		int[] path = new int[1000];
		printPaths(root, path,0);
	}
	/** 
	 Recursive printPaths helper -- given a node, and an array containing 
	 the path from the root node up to but not including this node, 
	 prints out all the root-leaf paths. 
	*/
	public void printPaths(Node node,int [] path, int pathLen){
		if(node == null){
			return;
		}
		// append this node to the path array 
		path[pathLen] = node.data;
		pathLen++;
		
		// it's a leaf, so print the path that led to here 
		if(node.left==null && node.right==null){
			printArray(path,pathLen);
			
		} else{
			printPaths(node.left,path,pathLen);
			printPaths(node.right,path,pathLen);
		}
	}
	
		public void printArray(int[] ints, int len){
			int i;
			for(i =0; i<len; i++){
				System.out.print(ints[i]+" ");
			}
			System.out.println();
		}
		/** 
		 Changes the tree into its mirror image.

		 So the tree... 
		       4 
		      / \ 
		     2   5 
		    / \ 
		   1   3

		 is changed to... 
		       4 
		      / \ 
		     5   2 
		        / \ 
		       3   1

		 Uses a recursive helper that recurs over the tree, 
		 swapping the left/right pointers. 
		*/ 
		public void mirror(){
			mirror(root);
		}
		
		public void mirror(Node node){
			if(node !=null){
				// do the sub-trees 
				mirror(node.left);
				mirror(node.right);
				
			}
			// swap the left/right pointers 
			Node temp = node.left;
			node.left =node.right;
			node.right=temp;
			
		}
	
	
		/** 
		 Changes the tree by inserting a duplicate node 
		 on each nodes's .left. 
		  
		 
		 So the tree... 
		    2 
		   / \ 
		  1   3

		 Is changed to... 
		       2 
		      / \ 
		     2   3 
		    /   / 
		   1   3 
		  / 
		 1

		 Uses a recursive helper to recur over the tree 
		 and insert the duplicates. 
		*/ 
		public void doubleTree(){
			doubleTree(root);
		}
	
		public void doubleTree(Node node){
			Node oldLeft;
			if(node==null){
				return;
			
			}
			// do the subtrees 
			doubleTree(node.left);
			doubleTree(node.right);
			// duplicate this node to its left 
			oldLeft = node.left;
			node.left = new Node(node.data);
			node.left.left=oldLeft;//?????? 2-2-1-1?
		}
	
		/* 
		 Compares the receiver to another tree to 
		 see if they are structurally identical. 
		*/ 
		public boolean sameTree(BinarySearchTree other){
			return(sameTree(root,other.root));
		}
		public boolean sameTree(Node a, Node b){
			if(a ==null && b == null){//both empty
				return true;
			
			}else if(a !=null && b!= null){
				return(a.data ==b.data && sameTree(a.left,b.left)&&sameTree(a.right,b.right));
						
			}else { //one empty, another not
				return false;
			}
			
			
		}
		
		/** 
		 For the key values 1...numKeys, how many structurally unique 
		 binary search trees are possible that store those keys?
		 Strategy: consider that each value could be the root. 
		 Recursively find the size of the left and right subtrees. 
		*/
		public static int countTree(int numKeys){
			if(numKeys <=1){
				return(1);
			}else{
				// there will be one value at the root, with whatever remains 
			    // on the left and right each forming their own subtrees. 
			    // Iterate through all the values that could be the root... 				
				int sum = 0;
				int left, right,root;
				
				for(root=1;root <=numKeys; root++){
					left = countTree(root-1);//when root =1. always return 1???????????????
					right = countTree(numKeys-root);
					sum = sum + left*right;//why left*right?????????????????
					
				}
				return sum;
			}
		}
		
		/** 
		 Tests if a tree meets the conditions to be a 
		 binary search tree (BST). 
		*/ 
		public boolean isBST1(){
			return(isBST1(root));
		}
		/** 
		 Recursive helper -- checks if a tree is a BST 
		 using minValue() and maxValue() (not efficient). 
		*/ 
		public boolean isBST1(Node node){
			if(node ==null){
				return true;
			}
			if (node.left != null && maxValue(node.left)> node.data){
				return false;
			}
			if (node.right != null &&minValue(node.right)<= node.data){
				return false;
			}
			  // check that the subtrees themselves are ok 
			return(isBST1(node.left) && isBST1(node.right));
		}
		
		/** 
		  Efficient BST helper -- Given a node, and min and max values, 
		  recurs down the tree to verify that it is a BST, and that all 
		  its nodes are within the min..max range. Works in O(n) time -- 
		  visits each node only once. 
		*/ 
		
		public boolean isBST2(){
			return(isBST2(root,Integer.MIN_VALUE,Integer.MAX_VALUE));
		}
		
		public boolean isBST2(Node node,int min, int max){
			if(node ==null){
				return true;
			
			}else{
				// left should be in range  min...node.data 
				boolean leftOk = isBST2(node.left,min,node.data);//why in this order?
				if(!leftOk){
					// if the left is not ok, bail out 
					return false;
				}
				// right should be in range node.data+1..max 
				boolean rightOk = isBST2(node.right,node.data+1,max);//why in this order?
				return(rightOk);
			}
		}
		
		
		
		
		
		
		
		
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
